#include <iostream>

using namespace std;

int n, m;
const int N = 2e3 + 10, M = 1e3 + 10, MOD = 1e8;
int f[N][M];
int c[N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> c[i];

	f[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			f[i][j] = (f[i - 1][j] + f[i - 1][((j - c[i] % m) % m + m) % m]) % MOD;
		}
	}
	cout << f[n][0] - 1 << endl;
	return 0;
}